/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/add-and-search-word
@Language: C++
@Datetime: 16-02-09 05:41
*/

class WordDictionary {
	static const int MAXLEN = 27;
    struct TriedNode{
        TriedNode *alpha[MAXLEN];	// 26 is '\0'
        TriedNode(){
            for(int i=0;i<MAXLEN;++i)
                alpha[i]=NULL;
        }
    };
    TriedNode *root;
    void postdelete(TriedNode *r){
        if (!r)
            return;
        for(int i=0;i<MAXLEN;++i)
			postdelete(r->alpha[i]);
        delete r;
    }
public:
    WordDictionary(){
        root=NULL;
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        // Write your code here
        if (!root)
            root = new TriedNode();
        TriedNode *cur = root;
        for(int i=0;i<word.length();++i){			
			if (!cur->alpha[word[i]-'a'])
				cur->alpha[word[i]-'a'] = new TriedNode();					
			cur = cur->alpha[word[i]-'a'];			
        }
		if (!cur->alpha[MAXLEN-1])
			cur->alpha[MAXLEN-1] = new TriedNode();
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
	bool searchcore(string &word,int pos,TriedNode *r){
		if (r==NULL)
			return false;
		if (pos==word.length())
			return r->alpha[MAXLEN-1];		
		
		if (word[pos]=='.'){
			int find;
			for(int i=0;i<MAXLEN-1;++i){
				if (!r->alpha[i])
					continue;
				find = searchcore(word,pos+1,r->alpha[i]);
				if (find)
					return true;
			}
			return false;
		}
		else if (r->alpha[word[pos]-'a'])
			return searchcore(word,pos+1,r->alpha[word[pos]-'a']);			
		return false;
	}
    bool search(string word) {
        // Write your code here
        return searchcore(word,0,root);
    }
    
    ~WordDictionary(){
        postdelete(root);
        root=NULL;
    }
};